题目描述
leetcode 第82题:删除排序链表中的重复元素 II
存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除链表中所有存在数字重复情况的节点,只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。
示例:
输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]
解题方法一
栈
原址题解
- 解题思路
使用栈
stack
来存储链表中的数字
定义变量pop
来表示每次出栈数字,初始为None
遍历链表head
若当前节点数字head.val
存在于栈中,更新出栈数字
若当前节点数字不等于出栈数字,将节点数字压栈
遍历完成,此时栈中都是不重复的数字,再将栈转为链表返回即可
- 复杂度
时间复杂度:O(n),n为链表的长度
空间复杂度:O(n),n为栈的大小
- 代码实现
1 | class Solution: |
1 | class Solution { |
解题方法二
链表
参照题解
- 解题思路
由于链表
head
的头节点可能会被删除
添加一个哑节点指向链表的头节点,得到新的链表dummy
使用指针cur
表示当前节点开始遍历链表
如果cur.next.val
等于cur.next.next.val
记下cur.next.val
为temp
,指针后移,将等于temp
的节点删除
反之将cur
指向cur.next
遍历完成,此时链表中剩余哑节点和不重复的节点
跳过哑节点,直接返回dummy.next
即可
- 复杂度
时间复杂度:O(n),n为链表的长度
空间复杂度:O(1)
- 代码实现
1 | class Solution: |
1 | class Solution { |